#include <iostream>
#include <string>
#include <vector>

using namespace std;

void getNext(vector<int> & next, const string & p)
{
    int i = 0;
    int j = 1;
    next[i] = 0;
    for(; j < p.size(); j++)
    {
        while (i > 0 && p[i] != p[j])
        {
            i = next[i - 1];
        }
        if(p[i] == p[j])
        {
            i++;
            next[j] = i;
        }
    }
}

class Solution 
{
public:
    int strStr(string haystack, string needle) 
    {
        if(needle.length() > haystack.length())
        {
            return -1;
        }
        if(needle.length() == 0)
        {
            return 0;
        }
        vector<int> next(needle.size());
        getNext(next, needle);
        for(int i = 0, j = 0; i < haystack.length(); i++)
        {
            while(haystack[i] != needle[j] && j > 0)
            {
                j = next[j - 1];
            }
            if(haystack[i] == needle[j])
            {
                j++;
            }
            if(j == needle.length())
            {
                return i - j + 1;
            }
        }
        return -1;
    }
};

#include <iostream>
#include <string>
using namespace std;

int main() {
    Solution sol;

    // 测试用例1：正常匹配
    string haystack1 = "hello";
    string needle1 = "ll";
    cout << "Test 1: " << sol.strStr(haystack1, needle1) << " (期望输出: 2)" << endl;

    // 测试用例2：无匹配
    string haystack2 = "aaaaa";
    string needle2 = "bba";
    cout << "Test 2: " << sol.strStr(haystack2, needle2) << " (期望输出: -1)" << endl;

    // 测试用例3：needle为空
    string haystack3 = "abc";
    string needle3 = "";
    cout << "Test 3: " << sol.strStr(haystack3, needle3) << " (期望输出: 0)" << endl;

    // 测试用例4：haystack和needle完全相同
    string haystack4 = "abc";
    string needle4 = "abc";
    cout << "Test 4: " << sol.strStr(haystack4, needle4) << " (期望输出: 0)" << endl;

    // 测试用例5：needle比haystack长
    string haystack5 = "a";
    string needle5 = "abc";
    cout << "Test 5: " << sol.strStr(haystack5, needle5) << " (期望输出: -1)" << endl;

    // 测试用例6：haystack为空
    string haystack6 = "";
    string needle6 = "a";
    cout << "Test 6: " << sol.strStr(haystack6, needle6) << " (期望输出: -1)" << endl;

    // 测试用例7：haystack和needle都为空
    string haystack7 = "";
    string needle7 = "";
    cout << "Test 7: " << sol.strStr(haystack7, needle7) << " (期望输出: 0)" << endl;

    return 0;
}
